package com.shadow.output.study.algorithm.sequence;

/**
 * KMP详解1：KMP算法是如何演化来的
 * KMP算法是一个串匹配算法，是“众所周知”的晦涩难懂的算法之一。
 * 就我个人感觉，其实只要了解它的演化过程，会发现它并没有那么难以理解。甚至可以说是相当容易理解的。
 * 为什么这么说呢，我们先看一下，一开始我们是怎么匹配的？
 *
 * 如下图：
 *                                             ti
 *                                             |
 * 假设文本串：t[n] = t[0],t[1],t[2],...,t[i-1],t[i],t[i+1],...,t[m],...,t[n]
 * 假设模式串：p[m] = p[0],p[1],p[2],...,p[i-1],p[i],p[i+1],...,p[m]  // 匹配a
 *                                             |
 *                                             pi
 *
 * 假设 p[i]之前都匹配，p[i]是第一个不匹配（失配）
 * 失配了怎么办呢?我们很自然地想到蛮力算法来解决。
 * 蛮力算法：模式串右移一位，比较指针 pi 置为 0， ti 回溯到 t[1]，再从 t[1] 位置开始比较，如下图：
 *                         ti
 *                         |
 * 假设文本串：t[n] = t[0],t[1],t[2],...,t[i-1],t[i],t[i+1],...,t[m],...,t[n]
 * 假设模式串：p[m] =      p[0],p[1],p[2],...,p[i-1],p[i],p[i+1],...,p[m]  // 匹配b
 *                         |
 *                         pi
 *
 * 问题：能否快速判断上述匹配（匹配b）是否成功？或者说，能否快速判断上述匹配是不成功的，从而直接跳过？
 * 答案是可以的！
 * 首先，ti 不回溯
 * 其次，利用上一次比较结果，如下图（省略pi）：
 *                                             ti
 *                                             |
 * 假设文本串：t[n] = t[0],t[1],t[2],...,t[i-1],t[i],t[i+1],...,t[m],...,t[n]
 * 假设模式串：p[m] = p[0],p[1],p[2],...,p[i-1],p[i],p[i+1],...,p[m]  // 匹配a
 * 假设模式串：p[m] =      p[0],p[1],...,p[i-2],p[i-1],p[i],p[i+1],...,p[m]  // 匹配b
 *
 * 看 ti 之前的比较：t[0]=p[0],...,t[i-1]=p[i-1]
 * 那么，在 ti 之前，匹配b 如果要匹配上，即 p[0]=t[1]=p[1],p[1]=t[2]=p[2],...,p[i-2]=t[i-1]=p[i-1]
 * 也就是说，模式串截止到 i 之前的串(下面我会简称之为 p[i]子串)，（长度为 i-1）前缀和（长度为 i-1）后缀要相同。
 * 换言之，p[i]子串，如果没有相同的前缀（长度为 i-1）和后缀（长度为 i-1），则这次匹配可以跳过！
 *
 * 同样的道理，模式串再右移一位（假设上一次没有相同的前后缀被快速跳过），
 * （ti 不回溯）p[i]子串，如果没有相同的前缀（长度为 i-2）和后缀（长度为 i-2），则这次匹配可以跳过！
 *                                             ti
 *                                             |
 * 假设文本串：t[n] = t[0],t[1],t[2],...,t[i-1],t[i],t[i+1],...,t[m],...,t[n]
 * 假设模式串：p[m] = p[0],p[1],p[2],...,p[i-1],p[i],p[i+1],...,p[m]  // 匹配a
 * 假设模式串：p[m] =           p[0],...,p[i-3],p[i-2],p[i-1],p[i],...,p[m]  // 匹配c
 * ...
 * 直到有相同的前后缀，那么这次匹配就不能跳过。而且只要从 ti 开始比较就好。
 * 因为我们是依次递减找相同的前后缀（从长度为 i-1, i-2,...），那么第一次遇到的相同前后缀，必定是最长相同前后缀。
 * 所以说，我们只要研究模式串的最长相同前后缀，就能让模式串（在失配时）快速跳过一些不必要的匹配。
 * 举个例子:
 *
 *                                                ti
 *                                                |
 * 假设文本串：t[n] = P, x[1], x[2], ..., x[k], P, t[i], ...
 * 假设模式串：p[m] = P, x[1], x[2], ..., x[k], P, p[i], ...
 * 假设 P 是 p[i]子串的最长相同前后缀 P(0~n个字符)，
 * 在 ti 处失配，则可以快速跳过 x[1],x[2],...,x[k] 的比较，以“模式串的前缀P”对齐“文本串的后缀P” 在 ti 处继续比较，如下图：
 *                                                ti
 *                                                |
 * 假设文本串：t[n] = P, x[1], x[2], ..., x[k], P, t[i], ...
 * 假设模式串：p[m] =                           P, x[1], x[2], ..., x[k], P, p[i], ...
 *
 * 这就是 KMP 算法的核心！！（KMP来自发明此算法的三位科学家名字的首字母）
 *
 * 不知你是否依然担心快速跳过这么多的比较，会不会有一些正确的匹配被错过了呢？
 * 答案是不会错过的。但如果你依然有所担心，我们还可以从反向推导。（一开始是正向推导，从蛮力算法演化到KMP算法）
 *
 * 还是上面的例子（已知：P 是 p[i]子串的最长相同前后缀）
 * 假设会错过正确的匹配，而错过的匹配（从x[j]开始匹配上了）如下图：
 *                                                                 ti(失配处)
 *                                                                 |
 * 假设文本串：t[n] = P, x[1], x[2], ..., x[j], ........., x[k], P, t[i], ...
 * 假设模式串：p[m] = P, x[1], x[2], ..., x[j], ........., x[k], P, p[i], ...  // x[j]到 P 为后缀
 * 假设模式串：p[m] =                     P, x[1], x[2], ..., x[k-j+1], x[k-j+2], ... // P 到 x[k-j+1]为前缀
 *
 * 如果说从x[j]处可以匹配上，那么对于 p[i]子串来说，x[j] 到 P 是为后缀，P 到 x[k-j+1] 是为前缀，这两部分是相同的！！
 * 也就是说，P 不是最长的相同前后缀！这与已知（P 是 p[i]子串的最长相同前后缀）矛盾！！
 * 所以假设会错过正确的匹配是不成立的！
 *
 *
 * ok, KMP的核心算法到此就结束了！
 *
 *
 * 但是我们要怎么把算法变成代码呢？在变成代码之前，我们要先知道，在失配时，我们可以快速移动多少位置？
 * 如下图，（式b）到（式c）移动了多少位置？
 *                                                ti
 *                                                |
 * 假设文本串：t[n] = P, x[1], x[2], ..., x[k], P, t[i], ...  //（式a）
 * 假设模式串：p[m] = P, x[1], x[2], ..., x[k], P, p[i], ...  // (式b)
 * 假设模式串：p[m] =                           P, x[1], x[2], ..., x[k], P, p[i], ... // (式c)
 *                                                |
 *                                                pi
 *
 * 因为对齐关系，我们可以只看（式a）的前一个 P 到后一个 P 移动了多少
 * 假设在 p[i] 处失配，我们需要知道 p[i] 子串的最长相同前后缀的长度（即 P 的长度），假设是 n，
 * 那么（式a）后一个 P 到 t[i] 长度为 n + 1，
 * 所以（式a）后一个 P 的首位下标为 (i-n)。 i - ? + 1 = n + 1 => ? = i - n
 * 所以 P 是从 0 快速移动到了 (i-n)。
 *
 * 那代码里要怎么体现这个“移动”呢？
 * 当在 p[i] 处失配，只要把 pi 指向 x[1] 处即可。从 ti 和 pi 指向的字符继续比较。
 * 那 x[1] 的下标是多少呢？
 * 因为 P 的长度是 n（最长相同前后缀），那么 x[1] 的下标就是 n，即 pi = n，继续跟ti处比较。
 *
 * 所以对于每个 i，我们都需要知道 p[i] 子串的最长相同前后缀长度是多少？
 * 由每个p[i]子串对应的最长相同前后缀构成的数组，我们称之为 next 表。
 * 那我们如何求解 next 表呢？求解 next 表也是这个算法的一个难点。
 * 可能有些人看网上的求解 next 表的代码，感觉云里雾里，甚至做起人工 debug。debug完了之后依然有很多问号？？？？
 * 可能有些人看完之后，觉得似曾相识，和动态规划有点像？有没有？
 *
 * 就我个人而言，我觉得这个求解 next 表也是可以推导的，那要怎么推导呢？下个视频再见^_^
 *
 *
 *
 * KMP 详解2：如何推导 next 表
 * 最长相同前后缀（next表）：
 * 假设模式串：p[m] = p[0],p[1],p[2],...,p[n],...,p[i-1],p[i],p[i+1],...,p[m]  // 注意下标从0开始
 *
 * next[0]=?，肯定不是正数。
 * next[1]=0
 *
 * 条件： next[i] = n，求解 next[i+1]
 * next[i]表示 p[i] 子串（截止到 p[i] 的子串），最长的相同前后缀。
 * next[i+1]表示 p[i+1] 子串，最长的相同前后缀。
 * 假设最长长度为：x(即next[i+1]==x)，那么如下图前后缀要相同：
 *               p[0],    p[1],    p[2],    ...,p[x-2],    p[x-1] // 前缀 （式1）
 *               p[i-x+1],p[i-x+2],p[i-x+3],...,p[i-1],    p[i] // 后缀  （式2）
 *
 * 拆两部分看，一部分是前面 x-1 个字符（暂且称之为a部分），一部分是 p[x-1]=p[i]（b部分），哪一部分不相等都不行
 * 那我们要怎么求解这个 x 呢？
 *
 * 重点来了！！
 * 我的想法是尝试！因为我们是要找最长的相同前后缀，所以要让p[0]到p[x-2]尽可能长，最长有多长呢？
 * （式1）的前部分（a部分）其实是 p[i] 子串的某个前缀，
 * （式2）的前部分（a部分）其实是 p[i] 子串的某个后缀，
 * 它们要相等，最长有多长？
 * 这由 p[i]子串最长前后缀决定，就是next[i](即n)
 * 我们可以从长度为 n 开始，进行尝试！

 * 已知 next[i] = n，即 p[i] 的最长相同前后缀长度为 n，将n 代入，如下图（图1）：
 *               p[0],  p[1],    p[2],    ...,p[n-1],    p[x-1] // 前缀 （式1）
 *               p[i-n],p[i-n+1],p[i-n+2],...,p[i-1],    p[i] // 后缀  （式2）
 * 前部分已经相等了，如果这时 p[x-1] 与 p[i] 相等，即后部分（b部分）也相等，那么就求解完成！即有 x-1=n，从而 x=n+1
 * 如果这时 p[x-1] 与 p[i] 不相等，那么就以逐一递减的方式，进行尝试！
 * 什么叫以逐一递减的方式进行尝试？
 * 操作如下：
 * （式1）的前部分（a部分）去掉最后一个，（式2）的前部分（a部分）去掉最后一个，继续比较！如图（图2）：
 *               p[0],    p[1],    p[2],    ...,p[n-2],    p[x-1] // 前缀 （式1）
 *               p[i-n+1],p[i-n+2],p[i-n+3],...,p[i-1],    p[i] // 后缀  （式2）
 * 依然要比较前部分和后部分！如果（图2）（式1）和（式2）前部分和后部分都相等，那么这肯定是 p[i+1] 最长的相同前后缀！
 * 因为这是以逐一递减的方式进行尝试的！
 *
 * 当我们进行（图2）（式1）和（式2）的前部分进行比较时，有没有发现我们在干蠢事？
 * 因为（图1）告诉我们（p[i] 子串的最长相同前后缀长度为 n）：p[i-n+1]=p[1],p[i-n+2]=p[2],...,p[i-1]=p[n-1]
 * 代入（图2）（式2），可以得到如下图（图3）：
 *               p[0],p[1],p[2],...,p[n-2],    p[x-1] // 前缀 （式1）
 *               p[1],p[2],p[3],...,p[n-1],    p[i] // 后缀  （式2）
 * 发现没有？！
 * （图3）（式1）的前部分是截止到 p[n]的子串的最长前缀，（图3）（式2）的前部分是截止到 p[n]的子串的最长后缀，
 * 它们相不相等，由 p[n] 的最长相同前后缀（next[n]）说了算！
 * 假设 next[n]=k，那么可以跳过不必要的比较，得到如下图（图4）：
 *               p[0],  p[1],    p[2],    ...,p[k-1],    p[x-1] // 前缀 （式1）
 *               p[n-k],p[n-k+1],p[n-k+2],...,p[n-1],    p[i] // 后缀  （式2）
 *               p[0],  p[1],    p[2],    ...,p[k-1],    p[i] // 后缀  （式3：式2的变换）
 * 前部分已经相等了，如果这时 p[x-1] 与 p[i] 相等（即后部分（b部分）也相等），那么就求解完成！即有 x-1=k，从而 x=k+1=next[n]+1
 * 如果这时 p[x-1] 与 p[i] 不相等，那么就以逐一递减的方式，（式1）去掉 p[k-1]，（式3）去掉 p[0]，
 * 然后再次尝试，就变成尝试p[k]子串的最长相同前后缀了...，
 * 恭喜你，已经进入了一个循环！如果你感觉不到一个循环，请从“重点来了！！”重新看。
 *
 * 最后的结果有两种可能，
 * 1. 在某一次循环中得到结果退出。
 * 2. 前部分缩减到0，最后是比较p[i] 与 p[0]，如果相等，结果则为1，否则为0。
 *
 * 剩下两个问题
 * 1. next[0]=? 从上面的推导过程，会发现一开始求 next[i](=n)，再求 next[n](=k)，再再求 next[k](...)
 * i -> n -> k -> ... -> 0，我们最终会求 next[0]，如果 next[0]==0，就会进入死循环。（当然也可以做些判断避免）
 * 那 next[0]=任何负数？理论上可以，但为方便编程，我们设定 next[0]=-1。为什么这样设定会方便编程？这个等具体编程时再解释。
 *
 * 2. 那代码怎么写？
 * 1). 暴力递归
 * 2). 递归 + 备忘录（记忆化搜索）
 * 3). 迭代 （有没有动态规划的感觉）
 *
 *
 *
 * KMP 详解3：next表代码实现。
 *
 *
 */
public class KMP implements Sequence{

    public static int[] next(String pattern) {

        // 1. 暴力递归
//        char[] chars = pattern.toCharArray();
//        int[] next = new int[chars.length];
//        for (int i = 0; i < chars.length; i ++) {
//            next[i] = recursion(chars, i);
//        }
//        return next;

        // 2. 递归 + 备忘录（记忆搜索）
//        char[] chars = pattern.toCharArray();
//        int[] next = new int[chars.length];
//        // 初始化，next[0] = -1;next[1] = 0;next[2+] = -2;
//        next[0] = -1;
//        for (int i = 2; i < chars.length; i++) {
//            next[i] = -2;
//            memorandum(chars, i, next);
//        }
//        return next;


        // 3. 迭代
        return dp3(pattern);
    }

    //
    // 截止到index之前的串（即p[index]子串）的最长相同前后缀 递归
    // index 对应求解 i+1
    private static int recursion(char[] p, int index) {
        if (index < 2) {
            return index - 1; // 0:-1,1:0
        }

        int i = index - 1;
        int n = i;

        while (true) {
            n = recursion(p, n);
            // 1. 在某一次循环中得到结果退出。
            if (p[n] == p[i]) {
                return n + 1;
            }
            //2. 前部分缩减到0，最后是比较p[0] 与 p[i]，如果相等，结果则为1，否则为0。
            if (n == 0) {
                return 0;
            }
        }
    }

    // 递归+备忘录
    private static int memorandum(char[] p, int index, int[] next) {
        if (next[index] != -2) {
            return next[index];
        }
        int i = index - 1;
        int n = i;

        while (true) {
            n = memorandum(p, n, next);
            // 1. 在某一次循环中得到结果退出。
            if (p[n] == p[i]) {
                next[index] = n + 1;
                return next[index];
            }
            //2. 前部分缩减到0，最后是比较p[i] 与 p[0]，如果相等，结果则为1，否则为0。
            if (n == 0) {
                next[index] = 0;
                return next[index];
            }
        }
    }


    // 迭代
    private static int[] dp(String pattern) {
        char[] p = pattern.toCharArray();
        int length = p.length;
        int[] next = new int[length];
        next[0] = -1;
        if (length <= 2) {
            return next;
        }

        //
        int index = 2;

        int n = next[index - 1];
        while (index < length) {
            if (n < 0 || p[index-1] == p[n]) {
                next[index] = n + 1;
                index ++;
                n = next[index - 1];// next[index++]=++n
                continue;
            }
            // 可用小技巧：因为 next[0]=-1,next[1]=0, 可令两个条件合二为一
            // 当n=0时，继续走 n=next[n]（即 n=-1），那么 next[index++]=0(=++n)
//            if (n == 0) {
//                next[index] = 0;
//                index ++;
//                // n = next[index - 1] (=0)
//                continue;
//            }
            // 逐一递减的方式查找最长相同前后缀！
            n = next[n];
        }
        return next;
    }

    // 迭代
    private static int[] dp2(String pattern) {
        char[] p = pattern.toCharArray();
        int length = p.length;
        int[] next = new int[length];
        next[0] = -1;
        if (length <= 2) {
            return next;
        }

        int index = 2;
        int n = next[index - 1];
        while (index < length) {
            // 这里总是要减一，有没有办法优化呢？
            // index=index-1，即index从1开始，注意index++要改++index，且条件要改成index<length-1,：dp3
            if (n < 0 || p[index-1] == p[n]) {
                next[index++] = ++n;
            } else {
                // 逐一递减的方式查找最长相同前后缀！
                n = next[n];
            }
        }
        return next;
    }

    // 迭代
    private static int[] dp3(String pattern) {
        char[] p = pattern.toCharArray();
        int length = p.length;
        int[] next = new int[length];
        next[0] = -1;
        if (length <= 2) {
            return next;
        }

        int index = 1;
        int n = next[index];
        int iMax = length - 1;
        while (index < iMax) {
            if (n < 0 || p[index] == p[n]) {
                next[++index] = ++n;
            } else {
                // 逐一递减的方式查找最长相同前后缀！
                n = next[n];
            }
        }
        return next;
    }

    @Override
    public int indexOf(String text, String pattern) {
        if (null == text || null == pattern) {
            return -1;
        }
        char[] tchars = text.toCharArray(), pchars = pattern.toCharArray();
        if (tchars.length == 0 || pchars.length == 0 || tchars.length < pchars.length) {
            return -1;
        }
        // 得到 next 表
        int[] next = next(pattern);

        int pi = 0, ti = 0;
        int max = tchars.length - pchars.length;
        // ti - pi：为一轮比较中，text文本串首个比较字符的下标。
        while (pi < pchars.length && ti - pi <= max) {
            if (pi < 0 || pchars[pi] == tchars[ti]) {
                pi ++;
                ti ++;
            } else {
                // 在p[i] 处失配，pi快速移动！ti不回溯
                // 由 next[pi] 保证，pi 之前的不需要再比较！
                pi = next[pi];
            }
        }

        return pi == pchars.length ? ti - pi : -1;
    }
}

